In recent years, along with the trend for networking built-in devices typically including mobile telephones, the necessity increases for the built-in devices to conduct a process concerning the information security in order to maintain the confidentiality and the integrity of data dealt with by the built-in devices and to authenticate the built-in devices themselves. The process concerning the information security is implemented by a cryptographic algorithm and authentication algorithm. Execution of such algorithms basically requires that each built-in device hold its unique confidential information and an identifier specific to the device “securely”. “Securely” signifies that a person other than the authorized user of the built-in device cannot read or tamper the identifier easily.
A means for holding the identifier securely includes a protection method that uses a housing on which various types of sensors (a photosensor, a voltage sensor, and a frequency detector) are mounted to prevent an external unauthorized access using a physical protection film (a metal case or resin molding), and a protection method that uses an anti-tamper mechanism such as a security chip. These protection methods presume that they protect an identifier that exists in the device in a nonvolatile manner as digital data.
As a method that securely holds an identifier with an approach different from the above-mentioned means, a technology called PUF (Physical Unclonable Function) is available. The significant feature of the PUF resides in that the identifier is not held in the device as nonvolatile digital data. The PUF is practiced in several manners which are typically represented by “A signal generator based device security” disclosed in Patent Literature 1 and “A semiconductor device identifier generation method and semiconductor device” disclosed in Patent Literature 2.
The feature of an identifier generated by the PUF as in Patent Literature 1 or 2 resides in that a unique bit string is not always generated each time an identifier is generated. That is, the identifier is generated as data including noise. A technology described in Patent Literature 1, of converting an identifier including noise into unique data will be described hereinafter.
In Patent Literature 1, first, identifier generation is divided into two steps (“initial generation” and “re-generation”). A bit string generated in initial generation serves as the identifier of a device. In re-generation, a process of generating the same bit string as the bit string generated in initial generation is conducted.
<Initial Generation Step>
First, a bit string is generated by the PUF. As a simple example, 5-bit data is generated. The bit string will be defined as:
w=(w1, w2, w3, w4, w5)=10110
Then, auxiliary data s of this bit string is calculated. Note that the calculation is conducted using a (5, 1, 5) repetition code.
In this case, the following 4-bit bit string is obtained:
s=(w1 xor w2, w1 xor w3, w1 xor w4, w1 xor w5)=1001
The auxiliary data calculation method depends on the structure of an error correction code employed. The auxiliary data is data that may be disclosed and is stored in a nonvolatile area. That is, the nonvolatile area to store the auxiliary data need not be a secure environment.
<Re-Generation Step>
In the re-generation step, a bit string and auxiliary data are generated by the PUF in the same manner as in initial generation. This bit string will be defined as:
w′=(w′1, w′2, w′3, w′4, w′5)=10000
In this example, data which is different by 2 bits from w generated in the initial generation step is outputted. This error in the bit string corresponds to the noise described above. Auxiliary data s′ of w′ is:
s′=1111
Then, s calculated and stored in the initial generation step is read out, and
e=s xor s′
is calculated.
Namely,
                    e        =                ⁢                  s          ⁢                                          ⁢          xor          ⁢                                          ⁢                      s            ′                                                  =                ⁢                  1001          ⁢                                          ⁢          xor          ⁢                                          ⁢          1111                                        =                ⁢        0110                                =                ⁢                  (                                    e              ⁢                                                          ⁢              1                        ,                                                  ⁢                          e              ⁢                                                          ⁢              2                        ,                                                  ⁢                          e              ⁢                                                          ⁢              3                        ,                          e              ⁢                                                          ⁢              4                                )                    
Then, the error bit position of w′ is specified by the following procedure.
Note that
SUM(e1, e2, e3, e4)=e1+e2+e3+e4,
SL(e1, e2, e3, e4)=(e1 xor e2, e1 xor e3, e1 xor e4, e1)
<Step 1>
SUM(e1, e2, e3, e4)=2
This indicates that the condition of being less than 3 is satisfied. Hence, w′1 is not wrong.
<Step 2>
(e1, e2, e3, e4)<=SL(e1, e2, e3, e4)=1100
SUM(e1, e2, e3, e4)=2
This indicates that the condition of being less than 3 is satisfied. Hence, w′2 is not wrong.
<Step 3>
(e1, e2, e3, e4)<=SL(e1, e2, e3, e4)=0111
SUM(e1, e2, e3, e4)=3
This indicates that the condition of being less than 3 is not satisfied. Hence, w′3 is wrong.
<Step 4>
(e1, e2, e3, e4)<=SL(e1, e2, e3, e4)=1110
SUM(e1, e2, e3, e4)=3
This indicates that the condition of being less than 3 is not satisfied. Hence, w′4 is wrong.
<Step 5>
(e1, e2, e3, e4)<=SL(e1, e2, e3, e4)=0011
SUM(e1, e2, e3, e4)=2
This indicates that the condition of being less than 3 is satisfied. Hence, w′5 is not wrong.
In accordance with the above checking result, w′ is corrected. In this case, w′ is corrected to 10110. This bit string is equal to w generated in initial generation.
In this manner, by conducting a process utilizing an error correction code, an identifier including noise can be converted into unique data.
If, in the above example, 3 bits are regenerated incorrectly, w cannot be correctly restored from w′. Namely, if noise exceeding the correction capability of a code that forms auxiliary data occurs in the regeneration step, an identifier cannot be generated correctly. For this reason, the error correction code used in the above process must have a correction capability determined by taking into account the error probability of the PUF.
The error probability of the PUF will be described. One major factor that increases the error probability of the PUF is a change in operating environment of the PUF with respect to the initial generation step as a criterion. A change in operating environment includes a temperature change, a voltage change, a deterioration over time of the semiconductor device, and the like.
In addition to a random factor that occurs momentarily, the change in operating environment includes chronological variations such as diurnal variations, seasonal variations, and deterioration over time.